
//Copyright 1997-2009 Syrinx Development, Inc.
//This file is part of the Syrinx Web Application Framework (SWAF).
// == BEGIN LICENSE ==
//
// Licensed under the terms of any of the following licenses at your
// choice:
//
//  - GNU General Public License Version 3 or later (the "GPL")
//    http://www.gnu.org/licenses/gpl.html
//
//  - GNU Lesser General Public License Version 3 or later (the "LGPL")
//    http://www.gnu.org/licenses/lgpl.html
//
//  - Mozilla Public License Version 1.1 or later (the "MPL")
//    http://www.mozilla.org/MPL/MPL-1.1.html
//
// == END LICENSE ==
using System;
using System.Collections;
using System.IO;
using System.Text.RegularExpressions;
using System.Xml;


using Swaf.Config;

namespace Swaf.Resource
{
	/// <summary>Parses a <em>Pattern</em> into a "regular expression".</summary>
	/// <remarks>
	/// <p>Grammar:
	/// <ul>
	/// <li>A <em>Pattern</em> is an <em>Alternation</em>.</li>
	/// <li>An <em>Alternation</em> is one or more <em>Sequences</em>, separated by a <c>|</c>.</li>
	/// <li>A <em>Sequence</em> is zero or more <em>Atoms</em>, not separated by anything.</li>
	/// <li>An <em>Atom</em> is one of the following:
	/// <ul>
	/// <li>A <em>Simple-Keyword</em>: a <c>{</c>, a keyword name, then a <c>}</c>.</li>
	/// <li>A <em>Composite Keyword</em>: a <c>{</c>, a keyword name, a space, an <em>Alternation</em>, then a <c>}</c>.</li>
	/// <li>A <em>Memo</em>: a <c>(</c>, an <em>Alternation</em>, then a <c>)</c>.</li>
	/// <li>A <em>Character Literal</em>: any character other than <c>(</c>, <c>)</c>, <c>{</c>, or <c>}</c>.</li>
	/// </ul>
	/// </li>
	/// </ul>
	/// </p><p>
	/// The main thing this class does is to translate <em>Patterns</em> into
	/// <em>Perl5 Regular Expressions</em>.  The following is a (greatly) simplified version
	/// of the <em>Perl5 Regular Expression</em> grammar:
	/// <ul>
	/// <li>A <em>Regexp</em> is an <em>RE-Alternation</em>.</li>
	/// <li>An <em>RE-Alternation</em> is one or more <em>RE-Sequences</em>, separated by a <c>|</c>.</li>
	/// <li>An <em>RE-Sequence</em> is zero or more <em>RE-Atoms</em>, not separated by anything.</li>
	/// <li>An <em>RE-Atom</em> is one of a gazillion things (too many to list here).</li>
	/// </ul>
	/// </p><p>
	/// Perhaps the most important issue with respect to Perl5 Regular Expressions
	/// is the concept of <em>Loopable</em>:
	/// <ul>
	/// <li>Every <em>Loopable</em> fragment is an <em>RE-Atom</em>,
	/// but not every <em>RE-Atom</em> is <em>Loopable</em> fragment.</li>
	/// <li>A Perl5 Regular Expression fragment held in the <c>String</c> <c>a</c>
	/// is <em>Loopable</em> if and only if the string <c>a+"*"</c> would put a loop
	/// around the entire pattern contained in <c>a</c> (that is, if <c>a+"*"</c>
	/// is equivalent to <c>"(?:"+a+")*"</c>).</li>
	/// </ul>
	/// </p></remarks>
	public class PatternRepository : IConfigPartner
	{
		protected internal class AnonymousClassConfigHandler:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"what"};
			public AnonymousClassConfigHandler(PatternRepository enclosingInstance)
			{
				this.enclosingInstance = enclosingInstance;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				configInfo.checkIllegalAttributes(s_legalAttributes);
				string dumb = configInfo.getAttribute("what");
				string smart = configInfo.getChildText();
				enclosingInstance.loopOptimizations_[dumb] = smart;
			}
			private PatternRepository enclosingInstance;
		}

		protected internal class AnonymousClassConfigHandler1:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"name","pre","post","child","result"};
			public AnonymousClassConfigHandler1(PatternRepository enclosingInstance)
			{
				this.enclosingInstance = enclosingInstance;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				if (enclosingInstance.complexityMap_.Count == 0)
				{
					enclosingInstance.complexityMap_["none"] = PatternRepository.NONE;
					enclosingInstance.complexityMap_["atom"] = PatternRepository.LOOPABLE;
					enclosingInstance.complexityMap_["loop"] = PatternRepository.LOOPABLE;
					enclosingInstance.complexityMap_["loopable"] = PatternRepository.LOOPABLE;
					enclosingInstance.complexityMap_["seq"] = PatternRepository.SEQUENCE;
					enclosingInstance.complexityMap_["sequence"] = PatternRepository.SEQUENCE;
					enclosingInstance.complexityMap_["alt"] = PatternRepository.ALTERNATION;
					enclosingInstance.complexityMap_["alternation"] = PatternRepository.ALTERNATION;
					enclosingInstance.complexityMap_["any"] = PatternRepository.ANY;
				}
				configInfo.checkIllegalAttributes(s_legalAttributes);
				string name = configInfo.getAttribute("name");
				string pre = configInfo.getAttribute("pre");
				string post = configInfo.getAttribute("post");
				string child = configInfo.getAttribute("child");
				string result = configInfo.getAttribute("result");
				int childType = (int)enclosingInstance.complexityMap_[child];
				int complexity = (int)enclosingInstance.complexityMap_[result];
				if (childType != PatternRepository.NONE && childType != PatternRepository.LOOPABLE && childType != PatternRepository.ANY)
					xmlError(configInfo.Context, "child=\"" + child + "\": expected 'none' or 'atom' or 'any'");
				if (complexity != PatternRepository.LOOPABLE && complexity != PatternRepository.SEQUENCE && complexity != PatternRepository.ALTERNATION)
					xmlError(configInfo.Context, "result=\"" + result + "\": expected 'atom' or 'seq' or 'alt'");
				if (name.StartsWith("{"))
					xmlError(configInfo.Context, "name=\"" + name + "\": must be a regexp, not of the form \"{...}\"");
				try
				{
					enclosingInstance.registerComposite(name, pre, post, childType, complexity);
					//enclosingInstance.sortKeywords();
				}
				catch (PatternRepository.BadPattern e)
				{
					xmlError(configInfo.Context, e.Message, e);
				}
			}
			private PatternRepository enclosingInstance;
		}

		protected internal class AnonymousClassConfigHandler2:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"name","extra","HACK"};
			public AnonymousClassConfigHandler2(PatternRepository enclosingInstance)
			{
				this.enclosingInstance = enclosingInstance;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				configInfo.checkIllegalAttributes(s_legalAttributes);
				string name = configInfo.getAttribute("name");
				string extra = configInfo.getAttribute("extra");
				// HACK: the xml parser appears to make it impossible to put a "<" or "&lt;" into a #text field
				string newValue = configInfo.getAttribute("HACK");
				if (newValue == null)
					newValue = configInfo.getChildText();
				if (extra == null)
					extra = (name.StartsWith("{optional-") || name.StartsWith("{not-"))?"false":"true";
				if (newValue == null)
					newValue = "";
				if (!name.StartsWith("{") || !name.EndsWith("}"))
					xmlError(configInfo.Context, "name=\"" + name + "\": must be of the form \"{...}\"");
				name = name.Substring(1, (name.Length - 1) - (1));
				try
				{
					enclosingInstance.registerSimple(name, newValue, true);
					if (System.Boolean.Parse(extra))
					{
						enclosingInstance.registerSimple(name + "s", "{1+ " + newValue + "}", false);
						enclosingInstance.registerSimple("optional-" + name + "s", "{0+ " + newValue + "}", false);
						enclosingInstance.registerSimple("optional-" + name, "{0-1 " + newValue + "}", false);
						enclosingInstance.registerSimple("not-" + name, "{not " + newValue + "}", false);
					}
					//enclosingInstance.sortKeywords();
				}
				catch (PatternRepository.BadPattern e)
				{
					xmlError(configInfo.Context, e.Message, e);
				}
			}
			private PatternRepository enclosingInstance;
		}

		protected internal class AnonymousClassConfigHandler3:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"noisy"};
			public AnonymousClassConfigHandler3(PatternRepository enclosingInstance)
			{
				this.enclosingInstance = enclosingInstance;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				configInfo.checkIllegalAttributes(s_legalAttributes);
				enclosingInstance.noisy = Boolean.Parse(configInfo.getAttribute("noisy"));
			}
			private PatternRepository enclosingInstance;
		}

		private class RawPatternConfigHandler:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"pattern","regex","complexity"};
			public RawPatternConfigHandler(PatternRepository rep)
			{
				this.m_rep = rep;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				configInfo.checkIllegalAttributes(s_legalAttributes);
				m_rep.registerRawPattern(configInfo.getAttribute("pattern"), 
					configInfo.getAttribute("regex"), Int32.Parse(configInfo.getAttribute("complexity")));
			}
			private PatternRepository m_rep;
		}

		private class RawKeywordConfigHandler:ConfigHandler
		{
			protected static string[] s_legalAttributes = new string[]{"keyword","prefix","suffix","childType","complexity"};
			public RawKeywordConfigHandler(PatternRepository rep)
			{
				this.m_rep = rep;
			}
			public override void  executeBefore(IConfigElement configInfo)
			{
				configInfo.checkIllegalAttributes(s_legalAttributes);
				m_rep.registerRawKeyword(configInfo.getAttribute("keyword"), 
					configInfo.getAttribute("prefix"), configInfo.getAttribute("suffix"),
					Int32.Parse(configInfo.getAttribute("childType")),
					Int32.Parse(configInfo.getAttribute("complexity")));
			}
			private PatternRepository m_rep;
		}

		public virtual void registerForConfig(IConfigManager cm)
		{
			cm.registerHandler("...<PatternConfig> <LoopOptimization>", new AnonymousClassConfigHandler(this));				
			cm.registerHandler("...<PatternConfig> <Composite>", new AnonymousClassConfigHandler1(this));
			cm.registerHandler("...<PatternConfig> <Keyword>", new AnonymousClassConfigHandler2(this));
			cm.registerHandler("...<PatternRepositoryNoise>", new AnonymousClassConfigHandler3(this));
			cm.registerHandler("...<PatternConfig> <RawPattern>", new RawPatternConfigHandler(this));
			cm.registerHandler("...<PatternConfig> <RawKeyword>", new RawKeywordConfigHandler(this));
		}

		public void checkConfigStatus()
		{
		}


		public PatternRepository(IApplication app)
		{
			m_app = app;
			m_keywords = new ArrayList();
			patterns_ = new Hashtable();
		}

		public void sortKeywords()
		{
			m_keywords.Sort();
		}
		
		/// <summary>This gets thrown whenever a <c>String</c> pattern contains errors.
		/// </summary>
		[Serializable]
		public class BadPattern : BaseException
		{
			public BadPattern(string message):base(message)
			{
				Application.currentApp.Log.println(Application.NORMAL_STARTUP_LOG_LEVEL, "Throwing " + this);
			}

			public BadPattern(string message, Exception innerException):base(message, innerException)
			{
				Application.currentApp.Log.println(Application.NORMAL_STARTUP_LOG_LEVEL, "Throwing " + this);
			}

			public BadPattern(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) 
				: base(info, context)
			{
			}

		}

		internal void registerRawPattern(string pattern, string regex, int complexity)
		{
			patterns_[pattern] = new Pattern(this, pattern, regex, complexity);
		}

		internal void registerRawKeyword(string keyword, string prefix, string suffix, int childType, int complexity)
		{
			m_keywords.Add(new Keyword(this, keyword, prefix, suffix, childType, complexity));
		}

		public string generateRawPatternXml()
		{
			StringWriter writer = new StringWriter();
			XmlTextWriter xmlOut = new XmlTextWriter(writer);
			xmlOut.WriteStartElement("PatternConfig");
			foreach(Pattern p in patterns_.Values)
			{
				xmlOut.WriteStartElement("RawPattern");
				xmlOut.WriteAttributeString("pattern", p.pattern());
				xmlOut.WriteAttributeString("regex", p.regexpString());
				xmlOut.WriteAttributeString("complexity", p.complexity().ToString());
				xmlOut.WriteEndElement();

			}

			foreach(Keyword k in m_keywords)
			{
				xmlOut.WriteStartElement("RawKeyword");
				xmlOut.WriteAttributeString("keyword", k.keywordRegexp.ToString());
				xmlOut.WriteAttributeString("prefix", k.prefixRegexp);
				xmlOut.WriteAttributeString("suffix", k.suffixRegexp);
				xmlOut.WriteAttributeString("childType", k.childType.ToString());
				xmlOut.WriteAttributeString("complexity", k.complexity.ToString());
				xmlOut.WriteEndElement();
			}

			xmlOut.WriteEndElement();
			return writer.ToString();
		}
		
		
		/// <summary>Returns the Regex object associated with the specified regular expression <c>pattern</c>,
		/// string, but if <c>pattern</c> has errors, it does <em>not</em> throw an exception.
		/// This is used only when the caller is <em>sure</em> that the <c>pattern</c> is valid,
		/// typically when the <c>pattern</c> is a string literal.
		/// If there is an error in <c>pattern</c>, it puts a message in the log file.
		/// </summary>
		public Regex knownGoodPattern(string pattern)
		{
			try
			{
				return getPattern(pattern).regexpObject();
			}
			catch (Exception e)
			{
				Application.currentApp.Log.println(Application.NORMAL_STARTUP_LOG_LEVEL,"PatternRepository.knownGoodPattern(): " + e);
			}
			try
			{
				return getPattern("dummy").regexpObject();
			}
			catch (Exception e)
			{
				Application.currentApp.Log.println(Application.NORMAL_STARTUP_LOG_LEVEL,"PatternRepository.knownGoodPattern(): can't even compile \"dummy\": " + e);
			}
			return null;
		}
		
		/// <summary>Returns a human-readable explanation of what's wrong with the pattern,
		/// or returns null if the pattern is a valid regular expression.
		/// </summary>
		public string patternErrorMessage(string pattern)
		{
			try
			{
				getPattern(pattern);
			}
			catch (BadPattern e)
			{
				return e.Message;
			}
			return null;
		}

		/// <summary>Returns the <c>Pattern</c> object that corresponds to the <em>Pattern</em> in <c>pattern</c>.</summary>
		/// <remarks>
		/// <p>Postcondition:
		/// <ul>
		/// <li><c>get(p).pattern()</c> will be the same as <c>p</c>, the parameter <em>Pattern</em>.</li>
		/// <li><c>get(p).regexpString()</c>: the <em>Perl5 Regular Expression</em> in
		/// <c>String</c> form. E.g., all the <c>{keywords}</c> in <c>get(p).pattern()</c>
		/// will have been converted to the equivalent <em>Perl5 Regular Expression</em> format.</li>
		/// 
		/// <li><c>get(p).regexpObject()</c>: the compiled <em>Perl5 Regular Expression</em> in binary form.</li>
		/// <li><c>get(p).complexity()</c>:
		/// <c>LOOPABLE</c> if/only-if <c>get(p).regexpString()</c> is <em>Loopable</em>,
		/// <c>SEQUENCE</c> if/only-if <c>get(p).regexpString()</c> is an <em>RE-Sequence</em>, or
		/// <c>ALTERNATION</c> if/only-if <c>get(p).regexpString()</c> is an <em>RE-Alternation</em>.</li>
		/// </ul>
		/// </p></remarks>
		/// <param name="pattern">the string containing the <em>Pattern</em>
		/// (e.g., it is allowed to contain <c>{keywords}</c>).</param>
		public Pattern getPattern(string pattern)
		{
			Pattern p = (Pattern) patterns_[pattern];
			if (p == null)
			{
				p = new Pattern(this, pattern);
				patterns_[pattern] = p;
			}
			return p;
		}

		
		/// <summary>
		/// Registers a <em>Composite-Keyword</em> to be replaced by the specified "regular expressions".</summary>
		/// <param name="keywordRegexp">the <em>Perl5 Regular Expression</em> that represents the <em>inside</em> of the keyword.
		/// This must <em>not</em> include the opening "{", but it should include the
		/// " " that separates the keyword itself from the "child" pattern.
		/// E.g., the parameter for <em>Composite-Keyword</em> <c>{optional </c>
		/// must be <c>"optional "</c>, not <c>"\\{optional "</c>.
		/// </param>
		/// <param name="prefixRegexp"> A portion of the <em>Perl5 Regular Expression</em> that replaces this keyword.
		/// In particular, it is the fragment of the replacement that is to be inserted before the child's regexp.
		/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>"(?:"</c>.
		/// Must not be <c>null</c>.
		/// </param>
		/// <param name="suffixRegexp">
		/// A portion of the <em>Perl5 Regular Expression</em> that replaces this keyword.
		/// In particular, it is the fragment of the replacement that is to be inserted after the child's regexp.
		/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>")"</c>.
		/// Must not be <c>null</c>.
		/// </param>
		/// <param name="childType">indicates what the "child" pattern must be.
		/// Must one of these:
		/// <ul>
		/// <li><c>NONE</c> if there is no child to be parsed;</li>
		/// <li><c>LOOPABLE</c> if there must be a child and it must be a LOOPABLE;</li>
		/// <li><c>ANY</c> if there must be a child but it doesn't have to be LOOPABLE.</li>
		/// </ul>
		/// </param>
		/// <param name="complexity">indicates the complexity of the resulting <em>Perl5 Regular Expression</em>.
		/// Must be one of these:
		/// <ul>
		/// <li><c>LOOPABLE</c> if/only-if the resulting regexp is <em>Loopable</em>.</li>
		/// <li><c>SEQUENCE</c> if/only-if the resulting regexp is an <em>RE-Sequence</em>.</li>
		/// <li><c>ALTERNATION</c> if/only-if the resulting regexp is an <em>RE-Alternation</em>.</li>
		/// </ul>
		/// </param>
		public void  registerComposite(string keywordRegexp, string prefixRegexp, string suffixRegexp, int childType, int complexity)
		{
			// if (noisy) System.out.println("Define: " + keywordRegexp + "\n    as: /" + prefixRegexp + "{CHILD}" + suffixRegexp + "/ (childType=" + childType + ", complexity=" + complexity + ")\n");
			//m_keywords.Add(new Keyword(keywordRegexp, compileRegexp(keywordRegexp), prefixRegexp, suffixRegexp, childType, complexity));
			m_keywords.Add(new Keyword(this,keywordRegexp, prefixRegexp, suffixRegexp, childType, complexity));
		}

		/// <summary>Registers a <em>Simple-Keyword</em> to be replaced by the specified <em>Pattern</em>.
		/// </summary>
		/// <param name="keywordPattern">the <em>Pattern</em> of the <em>inside</em> of the keyword.
		/// This must <em>not</em> include the opening "{" or the trailing "}".
		/// E.g., the parameter for <em>Simple-Keyword</em> <c>{identifier}</c>
		/// must be <c>"identifier"</c>, not <c>"{identifier}"</c>.
		/// </param>
		/// <param name="replacePattern">the <em>Pattern</em> that replaces this keyword.
		/// Since this is a <em>Pattern</em>, it can contain <c>{keywords}</c>
		/// (as opposed to <em>Perl5 Regular Expression</em> characters).
		/// E.g., for <em>Simple-Keyword</em> <c>{identifier}</c>, this would be
		/// <c>"{letter|_}{0+ {letter|digit|_}}"</c>.
		/// Must not be <c>null</c>.
		/// </param>
		/// <param name="throwOnError">If <c>true</c>, throws a <c>BadPattern</c> when <c>replacePattern</c> has an error.
		/// If <c>false</c>, uses the return value to indicate whether or not there was an error (see "Returns", below).
		/// </param>
		/// <returns><c>null</c> on success, otherwise, if <c>throwOnError==false</c>,
		/// returns a human-readable error message describing what went wrong.
		/// 
		/// </returns>
		public string registerSimple(string keywordPattern, string replacePattern, bool throwOnError)
		{
			try
			{
				//Regex k = getPattern(keywordPattern).regexpObject();
				Pattern k = getPattern(keywordPattern);
				Pattern r = getPattern(replacePattern);
				// if (noisy) System.out.println("Define: " + k.getPattern() + "\n    as: /" + r.regexpString() + "/ (complexity=" + r.complexity() + ")\n");
				//m_keywords.Add(new Keyword(k.regexpString(), k.regexpObject(), r.regexpString(), null, PatternRepository.NONE, r.complexity()));
				m_keywords.Add(new Keyword(this,k.regexpString(), r.regexpString(), null, PatternRepository.NONE, r.complexity()));
			}
			catch (BadPattern e)
			{
				if (throwOnError)
					throw e;
				return e.Message;
			}
			return null;
		}
			

		/// <summary>
		/// Maps from a <em>Pattern</em> string to the corresponding <c>Pattern</c> object.</summary>
		protected internal IDictionary patterns_;

		/// <summary>The list of all Keyword objects in the order in which they were registered.</summary>
		protected internal ArrayList m_keywords;
		protected IApplication m_app;

		
		/// <summary>This class holds onto all the information about a given <em>Pattern</em>.
		/// </summary>
		public class Pattern
		{
			protected PatternRepository m_rep;
			protected internal string pattern_;
			protected internal string regexpString_;
			protected internal Regex regexpObject_;
			protected internal int complexity_;
			
			/// <summary>Constructs a <c>Pattern</c> object from the <em>Pattern</em> in <c>pat</c>.</summary>
			/// <remarks>
			/// <p>Postcondition:
			/// <ul>
			/// <li><c>this.pattern()</c> will be the same as <c>pat</c>, the original <em>Pattern</em>.</li>
			/// <li><c>this.regexpString()</c>: the <em>Perl5 Regular Expression</em> in
			/// <c>String</c> form.  E.g., all the <c>{keywords}</c> in
			/// <c>this.pattern()</c> will have been converted to the equivalent
			/// <em>Perl5 Regular Expression</em> format.</li>
			/// 
			/// <li><c>this.regexpObject()</c>: the compiled <em>Perl5 Regular Expression</em>
			/// in binary form.</li>
			/// 
			/// <li><c>this.complexity()</c>:
			/// <c>LOOPABLE</c> if/only-if <c>this.regexpString()</c> is <em>Loopable</em>,
			/// <c>SEQUENCE</c> if/only-if <c>this.regexpString()</c> is an <em>RE-Sequence</em>, or
			/// <c>ALTERNATION</c> if/only-if <c>this.regexpString()</c> is an <em>RE-Alternation</em>.</li>
			/// </ul></p></remarks>
			/// <param name="rep">The repository the pattern is to be associated with.</param>
			/// <param name="pat">the string containing the <em>Pattern</em>
			/// (e.g., it is allowed to contain <c>{keywords}</c>).</param>
			protected internal Pattern(PatternRepository rep, string pat)
			{
				m_rep = rep;
				pattern_ = pat;
				Parser p = new Parser(rep, pattern_);
				complexity_ = p.consumePattern(m_rep);
				regexpString_ = p.dest.ToString();
				//createPattern();
			}
			
			public Pattern(PatternRepository rep, string pattern, string regex, int complexity)
			{
				m_rep = rep;
				pattern_ = pattern;
				complexity_ = complexity;
				regexpString_ = regex;
				//regexpObject_ = new Regex(regex);
			}

			protected void createPattern()
			{
				regexpObject_ = m_rep.compileRegexp(regexpString_);
			}

			/// <summary>
			/// The original <em>Pattern</em> that was passed to the constructor.</summary>
			public virtual string pattern()
			{
				return pattern_;
			}
			
			/// <summary>The <em>Perl5 Regular Expression</em> that is equivalent to <em>Pattern</em> <c>this.pattern()</c>.
			/// E.g., all the <c>{keywords}</c> in <c>this.pattern()</c> will have been converted to
			/// the equivalent <em>Perl5 Regular Expression</em> format.
			/// </summary>
			public virtual string regexpString()
			{
				return regexpString_;
			}
			
			/// <summary>The binary format that is equivalent to <c>this.regexpString()</c>.
			/// </summary>
			public virtual Regex regexpObject()
			{
				if(regexpObject_ == null)
					createPattern();
				return regexpObject_;
			}
			
			/// <summary>Returns the complexity of <c>this.regexpString()</c></summary>
			/// <remarks>
			/// <ul>
			/// <li><c>LOOPABLE</c> if/only-if <c>this.regexpString()</c> is <em>Loopable</em>.</li>
			/// <li><c>SEQUENCE</c> if/only-if <c>this.regexpString()</c> is an <em>RE-Sequence</em>.</li>
			/// <li><c>ALTERNATION</c> if/only-if <c>this.regexpString()</c> is an <em>RE-Alternation</em>.</li>
			/// </ul>
			/// </remarks>
			public virtual int complexity()
			{
				return complexity_;
			}			
		}
		
		/// <summary>Remembers all the important information about a given keyword.
		/// </summary>
		public class Keyword : IComparable
		{			
			/// <summary>
			/// Constructs a <c>Keyword</c> object using the specified <em>Perl5 Regular Expressions</em>.</summary>
			/// <param name="keyword">a compiled regular expression that matches the <em>inside</em> of the keyword.
			/// This must <em>not</em> include the opening "{" nor (in the case of a
			/// <em>Simple-Keyword</em>) the trailing "}".  However it should include
			/// the trailing <c>" "</c> in the case of a <em>Composite-Keyword</em>.
			/// E.g., the parameter for <em>Simple-Keyword</em> <c>{identifier}</c>
			/// must be compiled from <c>"identifier"</c>, not <c>"\\{identifier\\}"</c>.
			/// </param>
			/// <param name="prefixRegexp">
			/// A portion of the <em>Perl5 Regular Expression</em> that replaces the keyword.
			/// <p>For <em>Simple-Keywords</em>, this is generally the entire replacement for the keyword.
			/// Example: for <em>Simple-Keyword</em> <c>{digit}</c>, this would be <c>"\\d"</c>.</p>
			/// <p>For <em>Composite-Keywords</em>, this is the regexp fragment that goes before the regexp
			/// that results from translating the <em>Composite-Keyword's</em> "child".
			/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>"(?:"</c>.</p>
			/// <p>This must not be <c>null</c>.</p>
			/// </param>
			/// <param name="suffixRegexp">
			/// A portion of the <em>Perl5 Regular Expression</em> that replaces the keyword.
			/// <p>For <em>Simple-Keywords</em>, this is generally <c>null</c>.</p>
			/// <p>For <em>Composite-Keywords</em>, this is the regexp fragment that goes after the regexp
			/// that results from translating the <em>Composite-Keyword's</em> "child".
			/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>")"</c>.
			/// </p><p>
			/// When this is <c>null</c>, it means there is no child -- that this is a <em>Simple-Keyword</em>.</p></param>
			/// <param name="childType">indicates what the "child" pattern must be.
			/// Must one of these:
			/// <ul>
			/// <li><c>NONE</c> if there is no child to be parsed;</li>
			/// <li><c>LOOPABLE</c> if there must be a child and it must be a LOOPABLE;</li>
			/// <li><c>ANY</c> if there must be a child but it doesn't have to be LOOPABLE.</li>
			/// </ul>
			/// </param>
			/// <param name="complexity">indicates the complexity of the resulting <em>Perl5 Regular Expression</em>.
			/// Must be one of these:
			/// <ul>
			/// <li><c>LOOPABLE</c> if/only-if the resulting regexp is <em>Loopable</em>.</li>
			/// <li><c>SEQUENCE</c> if/only-if the resulting regexp is an <em>RE-Sequence</em>.</li>
			/// <li><c>ALTERNATION</c> if/only-if the resulting regexp is an <em>RE-Alternation</em>.</li>
			/// </ul>
			/// </param>
			//protected internal Keyword(string keywordStr, Regex keyword, string prefixRegexp, string suffixRegexp, int childType, int complexity)
			protected internal Keyword(PatternRepository rep, string keyword, string prefixRegexp, string suffixRegexp, int childType, int complexity)
			{
				this.m_rep = rep;
				this.m_keyword = keyword;
				//this.keywordRegexp = keyword;
				this.prefixRegexp = prefixRegexp;
				this.suffixRegexp = suffixRegexp;
				this.childType = childType;
				this.complexity = complexity;
			}
			
			protected PatternRepository m_rep;
			protected string m_keyword;
			/// <summary>Regular expression pattern that matches the beginning of the keyword.
			/// This must not match the opening "{" nor (in the case of a <em>Simple-Keyword</em>)
			/// the trailing "}".  However in the case of a <em>Composite-Keyword</em>, it should
			/// match the " " that separates the keyword itself from the "child" pattern.
			/// </summary>
			protected Regex m_keywordRegexp;
			
			public Regex keywordRegexp
			{
				get
				{
					if(m_keywordRegexp == null)
					{
						m_keywordRegexp = m_rep.compileRegexp(m_keyword);
					}
					return m_keywordRegexp;
				}
			}
			
			/// <summary>A portion of the <em>Perl5 Regular Expression</em> that replaces the keyword.</summary>
			/// <remarks>
			/// <p>For <em>Simple-Keywords</em>, this is generally the entire replacement for the keyword.
			/// Example: for <em>Simple-Keyword</em> <c>{digit}</c>, this would be <c>"\\d"</c>.</p>
			/// <p>For <em>Composite-Keywords</em>, this is the regexp fragment that goes before the regexp
			/// that results from translating the <em>Composite-Keyword's</em> "child".
			/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>"(?:"</c>.</p>
			/// <p>This is never <c>null</c>.</p></remarks>
			internal string prefixRegexp;
			
			/// <summary>A portion of the <em>Perl5 Regular Expression</em> that replaces the keyword.</summary>
			/// <remarks>
			/// <p>For <em>Simple-Keywords</em>, this is generally <c>null</c>.</p>
			/// <p>For <em>Composite-Keywords</em>, this is the regexp fragment that goes after the regexp
			/// that results from translating the <em>Composite-Keyword's</em> "child".
			/// Example: for <em>Composite-Keyword</em> <c>{group ___}</c>, this would be <c>")"</c>.</p>
			/// <p>When this is <c>null</c>, it means there is no child -- that this is a <em>Simple-Keyword</em>.</p>
			/// </remarks>
			internal string suffixRegexp;
			
			/// <summary>Indicates what the "child" pattern (if any) must be.</summary>
			/// <remarks>
			/// One of:
			/// <ul>
			/// <li><c>NONE</c> if there is no child to be parsed;</li>
			/// <li><c>LOOPABLE</c> if there must be a child and it must be a LOOPABLE;</li>
			/// <li><c>ANY</c> if there must be a child but it doesn't have to be LOOPABLE.</li>
			/// </ul>
			/// </remarks>
			internal int childType;
			
			/// <summary>Indicates the complexity of the <em>Perl5 Regular Expressions</em>
			/// that are created using this keyword.</summary>
			/// <remarks>
			/// One of:
			/// <ul>
			/// <li><c>LOOPABLE</c> if/only-if the resulting regexp is <em>Loopable</em>.</li>
			/// <li><c>SEQUENCE</c> if/only-if the resulting regexp is an <em>RE-Sequence</em>.</li>
			/// <li><c>ALTERNATION</c> if/only-if the resulting regexp is an <em>RE-Alternation</em>.</li>
			/// </ul>
			/// </remarks>
			internal int complexity;			
			#region IComparable Members

			public int CompareTo(object obj)
			{
				int l  =String.Compare(this.m_keyword, ((Keyword)obj).m_keyword);
				if(l == 1)
					return -1;
				else if(l == -1)
					return 1;
				else
					return 0;
			}

			#endregion
		}
		
		public class Parser
		{
			protected PatternRepository m_rep;
			/// <summary>
			/// Constructs a <c>PatternRepository.Parser</c> that will parse the string <c>src</c>.
			/// </summary>
			public Parser(PatternRepository rep, string src)
			{
				m_rep = rep;
				this.src = src;
				this.end = src.Length;
				pos = 0;
				dest = new System.Text.StringBuilder();
			}
			
			/// <summary>
			/// Consumes the <em>Pattern</em> at the current position, and emits the appropriate 
			/// <em>Perl5 Regular Expression</em> into <c>dest</c>.</summary>
			/// <remarks>
			/// Stops when <c>pos == end</c>.
			/// </remarks>
			/// <returns>
			/// indicator of the complexity of the emitted <em>Perl5 Regular Expression</em>.
			/// LOOPABLE means it is <em>Loopable</em>,
			/// SEQUENCE means it is an <em>RE-Sequence</em>
			/// (2+ <em>Loopables</em> in a sequence),
			/// ALTERNATION means it is an <em>RE-Alternation</em>
			/// (2+ <em>RE-Sequences</em> separated by <c>'|'</c>).
			/// </returns>
			public virtual int consumePattern(PatternRepository rep)
			{
				// if (noisy) System.out.println("consumePat(): src[pos,end]=/" + src.substring(pos,end) + "/");
				int complexity = consumeAlternation(rep);
				if (pos < end)
					error("Unexpected '" + src[pos] + "'");
				// if (noisy) System.out.println("Pattern: /" + src + "/\n Regexp: /" + dest.toString() + "/\n");
				return complexity;
			}
			
			/// <summary>Consumes the <em>Alternation</em> at the current position,
			/// and emits the appropriate <em>Perl5 Regular Expression</em> into <c>dest</c>.
			/// Stops when <c>pos == end</c> or when <c>src.charAt(pos-1)</c> is <c>')'</c> or <c>'}'</c>.
			/// </summary>
			/// <returns>
			/// indicator of the complexity of the emitted <em>Perl5 Regular Expression</em>.
			/// LOOPABLE means it is <em>Loopable</em>,
			/// SEQUENCE means it is an <em>RE-Sequence</em>
			/// (2+ <em>Loopables</em> in a sequence),
			/// ALTERNATION means it is an <em>RE-Alternation</em>
			/// (2+ <em>RE-Sequences</em> separated by <c>'|'</c>).
			/// 
			/// </returns>
			protected internal virtual int consumeAlternation(PatternRepository rep)
			{
				// if (noisy) System.out.println("consumeAlt(): src[pos,end]=/" + src.substring(pos,end) + "/");
				int complexity = consumeSequence(rep);
				while (pos < end && src[pos] == '|')
				{
					complexity = PatternRepository.ALTERNATION;
					++pos;
					dest.Append('|');
					consumeSequence(rep);
				}
				return complexity;
			}
			
			/// <summary>Consumes the <em>Sequence</em> at the current position,
			/// and emits the appropriate <em>Perl5 Regular Expression</em> into <c>dest</c>.
			/// Stops when <c>pos == end</c> or when <c>src.charAt(pos-1)</c> is <c>'|'</c> or <c>')'</c> or <c>'}'</c>.
			/// </summary>
			/// <returns>
			/// indicator of the complexity of the emitted <em>Perl5 Regular Expression</em>.
			/// LOOPABLE means it is <em>Loopable</em>,
			/// SEQUENCE means it is an <em>RE-Sequence</em>
			/// (2+ <em>Loopables</em> in a sequence),
			/// ALTERNATION means it is an <em>RE-Alternation</em>
			/// (2+ <em>RE-Sequences</em> separated by <c>'|'</c>).
			/// 
			/// </returns>
			protected internal virtual int consumeSequence(PatternRepository rep)
			{
				// if (noisy) System.out.println("consumeSeq(): src[pos,end]=/" + src.substring(pos,end) + "/");
				int complexity = PatternRepository.LOOPABLE;
				int n;
				 for (n = 0; pos < end && src[pos] != '|' && src[pos] != ')' && src[pos] != '}'; ++n)
					complexity = System.Math.Max(complexity, consumeAtom(rep));
				if (n >= 2 && complexity == PatternRepository.LOOPABLE)
					complexity = PatternRepository.SEQUENCE;
				return complexity;
			}
			
			/// <summary>
			/// Consumes the <em>Atom</em> at the current position,
			/// and emits the appropriate <em>Perl5 Regular Expression</em> into <c>dest</c>.</summary>
			/// <remarks>
			/// <p>Precondition: <c>src.charAt(pos) == '{'</c>.</p>
			/// <p>Postcondition: <c>src.charAt(pos-1) == '}'</c>.</p>
			/// </remarks>
			/// <returns>
			/// indicator of the complexity of the emitted <em>Perl5 Regular Expression</em>.
			/// LOOPABLE means it is <em>Loopable</em>,
			/// SEQUENCE means it is an <em>RE-Sequence</em>
			/// (2+ <em>Loopables</em> in a sequence),
			/// ALTERNATION means it is an <em>RE-Alternation</em>
			/// (2+ <em>RE-Sequences</em> separated by <c>'|'</c>).
			/// <p>Note that <c>consumeAtom()</c> consumes a <em>Pattern Atom</em>,
			/// which doesn't always translate into an <em>RE-Atom</em>.
			/// In other words, this function will not always return LOOPABLE,
			/// since it might be the expansion of a {keyword} that is not LOOPABLE.
			/// </p></returns>
			protected internal virtual int consumeAtom(PatternRepository rep)
			{
				// if (noisy) System.out.println("consumeAtm(): src[pos,end]=/" + src.substring(pos,end) + "/");
				int complexity = PatternRepository.LOOPABLE;
				char c = src[pos++];
				switch (c)
				{
					case '(': 
						dest.Append('(');
						consumeAlternation(rep);
						dest.Append(')');
						consumeChar(')');
						break;
					
					case '{': 
						int p = pos;
						int l = dest.Length;
						try
						{
							complexity = consumeKeyword(rep);
							consumeChar('}');
						}
						catch(Exception e)
						{
							pos = p;
							dest.Length = l;
							rep.sortKeywords();
							complexity = consumeKeyword(rep);
							consumeChar('}');
						}
						break;
					
					case '.': case '^': case '$': case '*': case '+': case '?': case '\\': case '[': case ']': 
						dest.Append('\\').Append(c);
						break;
					
					case '}': case ')': case '|': 
						error("internal error in consumeAtom(rep)", pos - 1);
						break;
					
					default: 
						dest.Append(c);
						break;
					
				}
				return complexity;
			}
			
			/// <summary>Consumes the keyword at the current position,
			/// and emits the appropriate <em>Perl5 Regular Expression</em> into <c>dest</c>.</summary>
			/// <remarks>
			/// <p>Precondition: <c>src.charAt(pos-1) == '{'</c>.
			/// That is, we must be just <em>past</em> the keyword's "{".</p>
			/// <p>Postcondition: <c>src.charAt(pos) == '}'</c>.
			/// That is, we will be <em>at</em> the keyword's "}".</p>
			/// </remarks>
			/// <returns>
			/// indicator of the complexity of the emitted <em>Perl5 Regular Expression</em>.
			/// LOOPABLE means it is <em>Loopable</em>,
			/// SEQUENCE means it is an <em>RE-Sequence</em>
			/// (2+ <em>Loopables</em> in a sequence),
			/// ALTERNATION means it is an <em>RE-Alternation</em>
			/// (2+ <em>RE-Sequences</em> separated by <c>'|'</c>).
			/// </returns>
			protected internal virtual int consumeKeyword(PatternRepository rep)
			{
				// if (noisy) System.out.println("consumeKwd(): src[pos,end]=/" + src.substring(pos,end) + "/");
				
				// Find the "best" keyword (the one whose match is the longest):
				Keyword keyword = null;
				int longest = - 1;
				string group1 = null;
				string group2 = null;
				string srcFromPos = this.src.Substring(pos);
				foreach(Keyword k in rep.m_keywords)
				{
					Regex matcher = k.keywordRegexp;
					Match result = matcher.Match(srcFromPos);
					if(result.Success && result.Index == 0)
					{
						if (result.Length >= longest)
						{
							keyword = k;
							longest = result.Length;
							group1 = result.Groups[1].Value;
							group2 = result.Groups[2].Value;
						}
					}
				}
				if (keyword == null)
					error("Unknown {keyword}", pos - 1);
				if (longest == 0)
					error("Keyword \\{" + keyword.keywordRegexp.ToString() + "\\} matches zero characters", pos - 1);

				// Consume the keyword:
				pos += longest;
				
				// Prepend the keyword's prefix-regexp:
				int beginReplacement = dest.Length;
				dest.Append(keyword.prefixRegexp);
				
				// Figure out the keyword's suffix-regexp:
				string suffix = keyword.suffixRegexp;
				if (suffix != null && suffix.Length >= 1 && "{?+*".IndexOf((System.Char) suffix[0]) >= 0)
				{
					// Loop suffixes are: {n,m}, {n,m}?, {n,}, {n,}?, {n}, {n}?, ?, ??, +, +?, *, *?
					suffix = Cmn.replaceOneLiteral(suffix, "n", group1);
					suffix = Cmn.replaceOneLiteral(suffix, "m", group2);
					suffix = Cmn.replaceOneLiteral(suffix, "{0,1}", "?"); // e.g., "x{0,1}" ==> "x?"
					suffix = Cmn.replaceOneLiteral(suffix, "{0,}", "*"); // e.g., "x{1,}"  ==> "x+"
					suffix = Cmn.replaceOneLiteral(suffix, "{1,}", "+"); // e.g., "x{0,}"  ==> "x*"
					suffix = Cmn.replaceOneLiteral(suffix, "{1}", ""); // e.g., "x{1}"   ==> "x"
				}
				
				if (keyword.suffixRegexp == null)
				{
					// It's a simple-keyword; the work's already done
				}
				else if (keyword.prefixRegexp.Equals("[") || keyword.prefixRegexp.Equals("[^"))
				{
					// It's a {oneof ___} or {not-oneof ___}; parse the set of characters:
					char[] set = group1.ToCharArray();
					Array.Sort(set);
					int i = 0;
					while (i < set.Length)
					{
						char a = set[i++]; // first char in a range; e.g., "a-z"
						char z = a; // last char in a range; e.g., "a-z"
						while (i < set.Length && set[i] == z + 1)
						{
							z = set[i++];
						} // get last char in range; e.g., "a-z"
						string aStr = ((a == '[' || a == ']' || a == '\\' || a == '^' || a == '-')?"\\":"") + a;
						string zStr = ((z == '[' || z == ']' || z == '\\' || z == '^' || z == '-')?"\\":"") + z;
						dest.Append(aStr);
						if (z > a + 1)
							dest.Append('-');
						if (z != a)
							dest.Append(zStr);
					}
				}
				else if (suffix.Equals("regexp"))
				{
					// It's a {raw-loopable|___|} or {raw-sequence|___|} or {raw-alternation|___|}
					suffix = group2;
				}
				else if (keyword.childType != PatternRepository.NONE)
				{
					// It's a composite keyword; recurse to consume the "child":
					int childBegins = dest.Length;
					int childComplexity = consumeAlternation(rep);
					int childEnds = dest.Length;
					int childSize = childEnds - childBegins;
					if (childSize == 2 || (childSize == 3 && dest[childEnds - 3] == '\\'))
					{
						string dumb = "(?:x" + dest[childEnds - 1] + ")" + suffix;
						string smart = (string) rep.loopOptimizations_[dumb];
						if (smart != null)
						{
							// if (noisy) System.out.print("Pattern /" + src + "/: optimizing regexp /" + dest + "/ + /" + suffix + "/ ");
							dest.Remove(childEnds-1, 1);
							dest.Insert(childEnds-1, smart.Substring(1));
							// if (noisy) System.out.println("to /" + dest + "/");
							childComplexity = PatternRepository.LOOPABLE;
							suffix = "";
						}
					}
					if (keyword.childType == PatternRepository.LOOPABLE && childComplexity > PatternRepository.LOOPABLE)
						dest.Insert(childBegins, "(?:").Append(')');
				}
				
				// Append the keyword's suffix-regexp:
				if (suffix != null)
					dest.Append(suffix);
				
				// If the result is an alternation, wrap it: "a|b" ==> "(?:a|b)".
				if (keyword.complexity >= PatternRepository.ALTERNATION)
				{
					dest.Insert(beginReplacement, "(?:").Append(')');
					return PatternRepository.LOOPABLE;
				}
				
				return keyword.complexity;
			}
			
			/// <summary>Consumes the specified character.
			/// @throws PatternRepository.BadPattern if the "current character" is not equal to the specified character
			/// (i.e., if <c>this.src.charAt(this.pos) != c</c>).
			/// </summary>
			protected internal void  consumeChar(char c)
			{
				// if (noisy) System.out.println("consumeChr(): src[pos,end]=/" + src.substring(pos,end) + "/");
				if (pos < end && src[pos] != c)
					error("Expected '" + c + "'");
				++pos;
			}
			
			/// <summary>If the specified character is the current character, consumes it and returns <c>true</c>.
			/// That is, <c>this.pos</c> is incremented if and only if
			/// <c>this.src.charAt(this.pos) == c</c> at the beginning of this call.
			/// </summary>
			/// <returns><c>true</c> if and only if <c>this.src.charAt(this.pos) == c</c>.
			/// 
			/// </returns>
			protected internal bool consumeCharIfMatches(char c)
			{
				if (pos < end && src[pos] == c)
				{
					++pos;
					return true;
				}
				return false;
			}
			
			/// <summary>Throws a <c>PatternRepository.BadPattern</c> using the specified <c>details</c>.
			/// Called when there was a parse error at the implicit position, <c>this.pos</c>.
			/// </summary>
			protected internal virtual void  error(string details)
			{
				error(details, pos);
			}
			
			/// <summary>Throws a <c>PatternRepository.BadPattern</c> using the specified <c>details</c>.
			/// Called when there was a parse error at the specified position, <c>pos</c>.
			/// </summary>
			protected internal virtual void  error(string details, int pos)
			{
				string message = details + " at " + (pos >= end?"end of":"/" + src.Substring(pos, (end) - (pos)) + "/ in") + " pattern /" + src + "/";
				throw new BadPattern(message);
			}
			
			protected internal string src;
			protected internal int pos;
			protected internal int end;
			protected internal System.Text.StringBuilder dest;
		}
		
		
		/// <summary>Compiles the specified <em>Perl5 Regular Expression</em>.
		/// @throws BadPattern if <c>regexp</c> was an invalid <em>Perl5 Regular Expression</em>.
		/// </summary>
		internal Regex compileRegexp(string regexp)
		{
			Regex p = null;
			try
			{
				p = new Regex(regexp);
			}
			catch (ArgumentException e)
			{
				Application.currentApp.Log.println(Application.DEFAULT_FRAMEWORK_LOG_LEVEL,"Unexpected regexp error: regexp=/" + regexp + "/; error=" + e.Message);
				throw new BadPattern("Regexp/" + regexp + "/: " + e.Message);
			}
			return p;
		}
		
		
		/// <summary>Indicates the complexity of a regular expression.
		/// </summary>
		public const int LOOPABLE = 0;
		public const int SEQUENCE = 1;
		public const int ALTERNATION = 2;
		public const int NONE = 3;
		public const int ANY = 4;
		
		
		/// <summary>Maps from the name of the "complexity" constant to the constant itself
		/// (that is, one of LOOPABLE, SEQUENCE, ALTERNATION, NONE, or ANY).
		/// </summary>
		protected internal IDictionary complexityMap_ = new Hashtable();
		
		
		/// <summary>Determines whether or not the PatternRepository displays status on the log-file.
		/// </summary>
		protected internal bool noisy = false;
		
		
		/// <summary>Maps from a "dumb" loop-of-loop (e.g., "(?x+)?") to a "smart" replacement (e.g., "x*").
		/// Important: the 'smart' one must begin with 'x' and end with whatever.
		/// </summary>
		protected internal IDictionary loopOptimizations_ = new Hashtable();
		
		
	}
}